package ch4tree;

import java.util.ArrayList;
import java.util.HashMap;

import com.thoughtworks.xstream.XStream;
import com.thoughtworks.xstream.io.json.JettisonMappedXmlDriver;

public class Chapter {

	public static HashMap<Integer, TreeNode> createMinimalBST(int array[], boolean parent) {
		HashMap<Integer, TreeNode> result = new HashMap<>();
		addToTreeRecurse(array, 0, array.length - 1, parent, result);
		return result;
	}

	public static TreeNode createMinimalBST(int array[]) {
		return addToTree(array, 0, array.length - 1);
	}

	public static TreeNode addToTree(int arr[], int start, int end) {
		return addToTreeRecurse(arr, start, end, false, new HashMap<Integer, TreeNode>());
	}

	static TreeNode addToTreeRecurse(int[] arr, int start, int end, boolean parent, HashMap<Integer, TreeNode> map) {
		TreeNode n = createTreeMap(arr, start, end, parent, map);
		return n;
	}

	static TreeNode createTreeMap(int[] arr, int start, int end, boolean parent, HashMap<Integer, TreeNode> map) {
		if (start > end) {
			return null;
		}
		
		int mid = (start+end)/2;
		TreeNode n = new TreeNode(arr[mid]);
		n.left = addToTreeRecurse(arr, start, mid-1, parent, map);
		n.right = addToTreeRecurse(arr, mid+1, end, parent, map);
		
		if (parent) {
			if (n.left != null) {
				n.left.parent = n;
			}
			if (n.right != null) {
				n.right.parent = n;
			}
		}
		map.put(n.val, n);
		return n;
	}

	static HashMap<Integer, GraphNode> createGraph(int [] vertices, int [][] edges, boolean directed) {
		HashMap<Integer, GraphNode> map = new HashMap<>();
		for (int v : vertices) {
			GraphNode n = new GraphNode(v);
			map.put(v, n);
		}
		
		for (int [] e : edges) {
			GraphNode a = map.get(e[0]);
			GraphNode b = map.get(e[1]);
			a.getAdjacent().add(b);
			if (!directed) {
				b.getAdjacent().add(a);
			}
		}
		return map;
	}	
	
	static TreeNode rotateRight(TreeNode y) {
		TreeNode x = y.left;
		TreeNode r = x.right;
		x.right = y;
		y.left = r;
		TreeNode p = x.parent;
		if (p != null && y == p.left) {
			p.left = x;
		}
		else if (p != null && y == p.right) {
			p.right = x;
		}
		return x;
	}
	
	static TreeNode rotateLeft(TreeNode x) {
		TreeNode y = x.right;
		TreeNode r = y.left;
		y.left = x;
		x.right = r;
		TreeNode p = x.parent;
		if (p != null && x == p.left) {
			p.left = y;
			y.parent = p;
			x.parent = y;
		}
		else if (p != null && x == p.right) {
			p.right = y;
			y.parent = p;
			x.parent = y;
		}
		return y;
	}
	
	public static void main(String ...strings) {
		TreeNode bst = createMinimalBST(new int [] {1, 2, 3, 4, 5, 6});
        XStream xstream = new XStream(new JettisonMappedXmlDriver());
        xstream.setMode(XStream.ID_REFERENCES);
        xstream.alias("TreeNode", TreeNode.class);
        xstream.alias("GraphNode", GraphNode.class);

        String json = xstream.toXML(bst);
		System.out.println(json);
		
		BTreePrinter.printNode(bst);
		
		TreeNode rotateRight = rotateRight(bst);
		BTreePrinter.printNode(rotateRight);
		
		BTreePrinter.printNode(rotateLeft(rotateRight));
		
		TreeNode newBst = (TreeNode) xstream.fromXML(json);
		int x=0;
		
		GraphNode a = new GraphNode(1);
		GraphNode b = new GraphNode(2);
		a.getAdjacent().add(b);
		b.getAdjacent().add(a);
		
		ArrayList<GraphNode> nodes = new ArrayList<>();
		nodes.add(a);
		nodes.add(b);
		
		json = xstream.toXML(nodes);
		System.out.println(json);
	}

}
